'''
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

解题思路：递归于非递归
'''
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def isSymmetrical(self, pRoot):
        if not pRoot: return True
        return self.compare(pRoot.left, pRoot.right)

    def compare(self, left, right):
        if left and right:
            if right.val != left.val:
                return False
            if self.compare(left.left, right.right) and self.compare(left.right, right.left):
                return True
        elif not left and not right:
            return True
        else:
            return False


    # def isSymmetrical(self, pRoot):
    #     if not pRoot:return True
    #     cur = [pRoot]
    #     while cur:
    #         nextStack = []
    #         i, j = 0, 0
    #         # 按层遍历放入stack中为空也要放入None做占位符
    #         for i in range(len(cur)):
    #             if cur[i]:
    #                 nextStack.append(cur[i].left)
    #                 nextStack.append(cur[i].right)
    #             else:
    #                 nextStack.append(None)
    #                 nextStack.append(None)
    #         # 判断是否stack中是否全为空，全为空说明已经过了最后一行则跳出
    #         stack = list(filter(lambda x : x is not None, nextStack))
    #         if not stack: break
    #         # 循环判断数列是否对称
    #         for j in range(len(nextStack)):
    #             # 空值处理
    #             if nextStack[j] and nextStack[-j-1]:
    #                 if nextStack[j].val != nextStack[-j-1].val:return False
    #             # 若一个为空另一边不为空则直接跳出
    #             if (nextStack[j] and (not nextStack[-j-1])) or ((not nextStack[j]) and nextStack[-j-1]): return False
    #         cur = nextStack
    #     return True

a8 = TreeNode(8)
a61 = TreeNode(6)
a62 = TreeNode(6)
a51 = TreeNode(5)
a71 = TreeNode(7)
a72 = TreeNode(7)
a52 = TreeNode(5)
a53 = TreeNode(5)
a51.right = a53

a61.left = a51
a61.right = a71
a62.left = a72
a62.right = a52
a8.left = a61
a8.right = a62

s = Solution()
print(s.isSymmetrical(a8))